1. Field of the Invention
The present invention relates to calculating algorithms and, in particular, to calculating algorithms required for cryptographic applications.
2. Description of the Related Art
In particular in public key cryptography but also in other fields of cryptography, key lengths keep increasing. The reason for this is that the security requirements for such cryptographic algorithms keep increasing, too. With the RSA method as an example of an asymmetric cryptography concept, that is a public key method, the security against so-called brute force attacks increases with the key length used. Brute force attacks are attacks on a cryptographic algorithm, in which the key is to be derived by trying out all the possibilities. It is directly understandable that the time theoretically required for a brute force attack in order to try out all the possibilities strongly increases with an increasing key length.
It is to be mentioned in this context that RSA applications with key lengths of 512 bits used to be considered to be sufficient. Due to a technological and mathematical progress of the “opponent”, the key lengths for typical RSA applications have been increased to 1024 bits. In the meantime, some people even think that even this key length is not sufficient so that RSA key lengths of 2048 bits are aimed at.
When, on the other hand, existing cryptographic coprocessors, such as, for example, SmartCards, are considered, it can be seen that there is, of course, the desire to run RSA applications with key lengths of, for example, 2048 bits on cryptographic circuits which originally have only been developed for key lengths of, for example, 1024 bits. It is a characteristic of arithmetic coprocessors for existing SmartCard applications that they have been developed for fixed bit lengths which are not suitable for the latest security requirements, that is they are too small. This has the consequence that a 2048 bits RSA algorithm, for example, cannot be handled efficiently on 1024 bits coprocessors. For RSA applications, for example, the Chinese remainder theorem (CRT) is known, in which a modular exponentiation having a large key length is divided into two modular exponentiations having half the key length, according to which the results of the two modular exponentiations having half the length are summarized correspondingly.
It has been found out in recent times that the Chinese remainder theorem is especially susceptible to DFA attacks (DFA=differential fault analysis).
Thus, a problem in many methods is the “doubling” of the so-called modular multiplication, which is a central operation in cryptographic calculations. Thus a modular exponentiation can be divided into many modular multiplications, i.e., in an operation, in which a product of a first operand A and a second operand B is calculated in a remainder class regarding a modulus N. When the operands A and B each have 2 n bits, typical calculating units having a length of 2 n bits are used. These calculating units, due to their high length, are referred to as long number calculating units, which is, for example, in contrast to classic 8, 16, 32 or 64 bits architectures, which are, for example, employed for PC or workstation processors.
It is desired to execute a modular multiplication A*B mod N with numbers A, B and N of the bit length 2 n on an n bit calculating unit. This is very time-consuming since the numbers A, B, N, . . . can only be loaded in fragments, which is why conventional methods, provided they do not fail completely, are extensive from an organizational point of view and error-prone. In technology, there are several methods with which these problems have been solved so far. These methods are known under the key words Montgomery multiplication, normal multiplication, such as with a Karatsuba-Ofman and a later reduction, such as a Barret reduction.
A further concept in which a Montgomery calculation in a “CRT window” is used is illustrated in P. Pailler, “Low-cost double size modular exponentiation or how to stretch your cryptocoprocessor.”
All such concepts are extensive regarding the calculating time and the data organization and thus not always efficient.
In the German patent application, filed on the same day, (German Patent Application No. 102 19 158.1-53, filed Apr. 29, 2002) having the title “Vorrichtung und Verfahren zum Berechnen eines Ergebnisses einer modularen Multiplikation” (device and method for calculating a result of a modular multiplication), a concept in which a modular multiplication for operands of 2 n bits is transformed into several so-called MMD operations, for which operands having half the length, that is having n bits, are sufficient, is described. An MMD operation, apart from the remainder resulting from A×B mod N, also provides the result of the integer division, that is of the DIV operation, wherein this result is also referred to as the integer quotient Q.
In general the operation T mod N results in a remainder R when a term T regarding a modulus N is reduced. The operation T div N, however, provides the integer quotient regarding the modulus N so that the term T can be reconstructed from Q×N+R. The MMD operation (MMD=MultModDiv) thus serves to convert any term T into an integer quotient T and a remainder R regarding a modulus N.
In conventional modular arithmetics used for cryptography techniques, the result of the DIV operation, that is the integer quotient, is normally neither required nor calculated. The concept described above is, however, based on utilizing the DIV information, that is the integer quotient. In this way other applications in which not only the result of the MOD operation, that is the remainder, is required, but in which the integer quotient, that is the result of the DIV operation, is required as well can also exist in technology.